package PrefixSum$DoublePointer;

import java.util.*;

/**
 * 三数之和
 * https://leetcode-cn.com/problems/3sum/
 * 在数组中找出三个数，使得他们加起来的和为0
 * 借助两数之和的思路，要想让三数之和等于0，则固定好一个数num，另外两个数的和就等于 -num
 * 注意：1、返回所有符合条件的集合
 *      2、集合是不能够重复的，比如[-1,-1,2] 和 [1-,2,-1]就是幂等的，算作同一种情况
 * 测试案例：1、[-1,0,1,2,-1,-4]
 *         2、[0,0,0]
 *         3、[0,0,0,0]
 */
public class ThreeSum {
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++){
            if (i > 0 && nums[i] == nums[i - 1]) // 如果元素跟上一个元素相同，则已经统计过了，直接跳过
                continue;
            twoSum(nums, i + 1, -nums[i]);
        }
        return res;
    }

    /**
     * 双指针法计算两数之和
     * @param nums 原始数组
     * @param startIndex 数组起始位置
     * @param target 目标和
     */
    private void twoSum(int[] nums, int startIndex, int target){
        int j = nums.length-1;
        for (int i = startIndex; i < nums.length; i++) {
            if (i >= j) // 如果 i 比 j 大，则后面的都已经计算过了，直接返回即可
                break;
            if (i > startIndex && nums[i] == nums[i - 1]) // 去重
                continue;
            // nums 是有序的，如果最小值+最大值都比目标和要大，则将最大值减小一点，向左移动
            while (i < j && nums[i] + nums[j] > target)
                j--;
            if (i < j && nums[i] + nums[j] == target){
                res.add(new ArrayList<>(Arrays.asList(nums[startIndex - 1], nums[i], nums[j])));
            }
        }
    }
}
